#include <vector>
#include "math.h"

using namespace std;

class Solution {
public:
    // Dynamic Programming
    int numSquares(int n) {
        vector<int> nums(n+1, n+1);
        nums[0] = 0;  // 方便计算自己是平方数的情况
        for (int i=1; i<=n; ++i) {
            for (int j=1; j*j<=i; ++j) {  // j*j==i 为自己是平方数的情况
                nums[i] = min(nums[i], nums[i-j*j] + 1);
            }
        }
        return nums[n];
    }
};
